import javax.swing.tree.TreeCellRenderer;
import java.util.LinkedList;
import java.util.Queue;

public class Solution3 {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }
    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        boolean notComolete = false;//有一次机会
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if(cur == null){
                    notComolete = true;//cur为空可能是最后一个叶子结点了也可能就不是完全二叉树了
                    continue;
                }
                if(notComolete){
                    return false;
                }
                    queue.offer(cur.left);
                    queue.offer(cur.right);
            }
        }
        return true;
    }
}
